package com.cango.student.tree;

import java.util.LinkedList;

public class BinaryTree {
    /*
     * 先序遍历二叉树（递归）
     */
    public static void PrintBinaryTreePreRecur(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + " ");
            PrintBinaryTreePreRecur(root.left);
            PrintBinaryTreePreRecur(root.right);
        }
    }

    /*
     * 中序遍历二叉树（递归）
     */
    public static void PrintBinaryTreeMidRecur(TreeNode root) {
        if (root != null) {
            PrintBinaryTreeMidRecur(root.left);
            System.out.print(root.val + " ");
            PrintBinaryTreeMidRecur(root.right);
        }
    }

    /*
     * 后序遍历二叉树（递归）
     */
    public static void PrintBinaryTreeBacRecur(TreeNode root) {
        if (root != null) {
            PrintBinaryTreeBacRecur(root.left);
            PrintBinaryTreeBacRecur(root.right);
            System.out.print(root.val + " ");
        }
    }

    /*
     * 先序遍历二叉树（非递归）
     * 思路：对于任意节点T，访问这个节点并压入栈中，然后访问节点的左子树，
     *      遍历完左子树后，取出栈顶的节点T，再先序遍历T的右子树
     */
    public static void PrintBinaryTreePreUnrecur(TreeNode root) {
        TreeNode p = root;//p为当前节点
        LinkedList<TreeNode> stack = new LinkedList<>();
        //栈不为空时，或者p不为空时循环
        while (p != null || !stack.isEmpty()) {
            //当前节点不为空。访问并压入栈中。并将当前节点赋值为左儿子
            if (p != null) {
                stack.push(p);
                System.out.print(p.val);
                p = p.left;
            }
            //当前节点为空：
            //  1、当p指向的左儿子时，此时栈顶元素必然是它的父节点
            //  2、当p指向的右儿子时，此时栈顶元素必然是它的爷爷节点
            //取出栈顶元素，赋值为right
            else {
                p = stack.pop();
                p = p.right;
            }
        }
    }

    /*
     * 中序遍历二叉树（非递归）
     *
     * 思路：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，
     *       出栈，访问T->data，再中序遍历T的右子树。
     */
    public static void PrintBinaryTreeMidUnrecur(TreeNode root) {
        TreeNode p = root;//p为当前节点
        LinkedList<TreeNode> stack = new LinkedList<>();

        //栈不为空时，或者p不为空时循环
        while (p != null || !stack.isEmpty()) {
            //当前节点不为空。压入栈中。并将当前节点赋值为左儿子
            if (p != null) {
                stack.push(p);
                p = p.left;
            }
            //当前节点为空：
            //  1、当p指向的左儿子时，此时栈顶元素必然是它的父节点
            //  2、当p指向的右儿子时，此时栈顶元素必然是它的爷爷节点
            //取出并访问栈顶元素，赋值为right
            else {
                p = stack.pop();
                System.out.print(p.val);
                p = p.right;
            }
        }
    }

    /*
     * 后序遍历二叉树（非递归）
     *
     */
    public static void PrintBinaryTreeBacUnrecur(TreeNode root) {
        class NodeFlag<T> {
            TreeNode node;
            char tag;

            public NodeFlag(TreeNode node, char tag) {
                super();
                this.node = node;
                this.tag = tag;
            }
        }
        LinkedList<NodeFlag> stack = new LinkedList<>();
        TreeNode p = root;
        NodeFlag bt;
        //栈不空或者p不空时循环
        while (p != null || !stack.isEmpty()) {
            //遍历左子树
            while (p != null) {
                bt = new NodeFlag(p, 'L');
                stack.push(bt);
                p = p.left;
            }
            //左右子树访问完毕访问根节点
            while (!stack.isEmpty() && stack.getFirst().tag == 'R') {
                bt = stack.pop();
                System.out.print(bt.node.val);
            }
            //遍历右子树
            if (!stack.isEmpty()) {
                bt = stack.peek();
                bt.tag = 'R';
                p = bt.node;
                p = p.right;
            }
        }
    }

    /*
     * 层次遍历二叉树（非递归）
     */
    public static void PrintBinaryTreeLayerUnrecur(TreeNode root) {
       LinkedList<TreeNode> queue = new LinkedList<>();
       queue.offer(root);
       TreeNode p;
       while (!queue.isEmpty()) {
           p = queue.poll();
           System.out.print(p.val + " ");
           if (p.left != null) {
               queue.offer(p.left);
           }

           if (p.right!=null) {
               queue.offer(p.right);
           }
       }

    }
}
